package com.mlh.linkedlist;

//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
public class 删除链表的倒数第N个结点 {
	//一种常用的技巧是添加一个哑节点（dummy node），它的 next指针指向链表的头节点。
	public ListNode method1(ListNode head, int n) {
		//循环不变量
		//利用双指针来完成  front.next指的节点才是真实节点位置  behind也是
		// front指针先走n步 此时behind指针指向头结点
		ListNode front=new ListNode();
		ListNode behind=new ListNode();
		front.next=head;
		behind.next=head;
		for(int i=1;i<n;i++){
			front=front.next;
		}
		boolean flag=false;//用于标记是否进入while循环，如果没有进入，说明删除的是头结点
		//同时前进 前进到 front.next.next正好为null  此时 behind.next正好指向要删除节点
		while (front.next.next!=null){
			front=front.next;
			behind=behind.next;
			flag=true;
		}
		if(flag){
			behind.next=behind.next.next;
			return head;
		}else{
			return head.next;
		}
	}
	public ListNode practice(ListNode head, int n) {
		//利用哨兵节点
		//否则当n=1时，链表只有2个节点会出错
		//这是由于 这种情况本来应该是属于later.next= later.next.next;
		//但是由于数组的长度原因导致 没有进入while循环 变成了head.next; 导致出错
		//利用哨兵节点 就没有这个问题
		ListNode front=new ListNode(),later=new ListNode();
		front.next=later.next=head;
		//向后移动n-1个节点  指向正数第n个节点
		for (int i = 1; i < n; i++) {
			front=front.next;
		}
		boolean flag=false;
		while(front.next.next!=null){
			front=front.next;
			later=later.next;
			flag=true;
		}
		if(flag){
			later.next= later.next.next;
			return head;
		}
		return head.next;
	}

	//看力扣题解
	//让front.next指向head
	//sentry=front
	//later=head
	//让later移动n次
	// 然后循环移动到later为null 此时front.next指向要删除的节点
	//最后返回sentry.next即可
	//该方法可以解决 删除倒数第一个节点  或者链表只有一个节点的特殊情况
	public ListNode practice2(ListNode head, int n) {
		ListNode front=head,later=new ListNode(),sentry=later;
		later.next=head;
		for (int i = 0; i < n; i++) {
			front=front.next;
		}
		while(front!=null){
			front=front.next;
			later=later.next;
		}
		later.next=later.next.next;
		return sentry.next;
	}
}
